/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-12-04
 * Time: 上午 10:57
 */
public class Test5 {
    public static int reversePairs(int[] arr){
        if(arr.length<2){
            return 0;
        }//判断数组中是否有元素，或者仅有一个元素，不存在有序对
        int[] copy=arr.clone();
        return reversePairs(copy,0,arr.length-1);//开始进行递归
    }
    public static int reversePairs(int[] arr,int left,int right){
        if(left==right){
            return 0;
        }//递归出口
        int mid=left+(right-left)/2;
        int leftPairs=reversePairs(arr,left,mid);//左半部分的逆序对个数
        int rightPairs=reversePairs(arr,mid+1,right);//右半部分的逆序对个数
        int crossPairs=mergePairs(arr,left,mid,right);//跨中点的逆序对个数
        return leftPairs+rightPairs+crossPairs;//逆序对个数总和
    }
    public static int mergePairs(int[] arr,int left,int mid,int right){
        int[] tempArr=arr.clone();
        int i=left,j=mid+1,k=left,count=0;
        while(i<=mid&&j<=right){
            if(tempArr[i]>=tempArr[j]){
                arr[k]=tempArr[j];
                j++;k++;
                count+=mid-i+1;
            }else{
                arr[k]=tempArr[i];
                i++;k++;
            }
        }
        if(i==mid+1){
            for(; k<=right; k++){
                arr[k]=tempArr[j];
            }
        }
        if(j==right+1){
            for(;k<=right;k++){
                arr[k]=tempArr[i];
            }
        }
        return count;
    }
    public static void main(String[] args){
        int[] arr={3,2,9,1};
        int finall = reversePairs(arr);
        System.out.println("该数组逆序对的个数为 ："+finall);
    }
}
